Null Measurability at the Symmetrization Interface in VC Learning

• URL: http://arxiv.org/abs/2604.25028v1
• Date: Mon, 27 Apr 2026 22:10:34 GMT
• Title: Null Measurability at the Symmetrization Interface in VC Learning
• Abstract summary: 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.
• Score: 0.15229257192293197
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent work revisiting measurability in the fundamental theorem of statistical learning imposes Borel measurability of ghost-gap suprema. We show that, at the one-sided ghost-gap interface actually used by the standard symmetrization proof, this requirement is stronger than necessary. For any Borel-parameterized concept class on a Polish domain, the bad event "there exists a hypothesis whose ghost empirical error exceeds its training empirical error by at least ε/2" is analytic. By Choquet capacitability, it is therefore measurable in the completion of every finite Borel measure. We then construct a concept class whose bad event is null-measurable but not Borel, giving a strict separation from the Borel supremum condition. Finally, we prove closure under patching, fixed and countable interpolation, and fiber-product amalgamation, showing that the weaker regularity level is stable under natural concept-class constructors. In the realizable setting, where targets belong to the class and are measurable, these results weaken the measurability hypothesis needed by the symmetrization route from finite VC dimension to PAC learnability. The main results and the descriptive-set-theoretic infrastructure used by them are formalized in Lean 4.

Related papers

• A Borel Concept Class of VC Dimension One with a Non-PAC Consistent Learner in ZFC [0.0]
  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.
  arXiv  Detail & Related papers  (2026-08-31T04:56:40Z)
• Variational Inference for Evidential Deep Learning [69.9353638875714]
  We propose a mathematically principled framework, Variational Inference Evidential Deep Learning (VI-EDL)<n>VI-EDL achieves state-of-the-art performance in out-of-distribution detection, noise detection and autonomous driving scenario.
  arXiv  Detail & Related papers  (2026-05-26T02:32:59Z)
• The Price of Robustness: Stable Classifiers Need Overparameterization [17.335490896384265]
  We establish a generalization bound for finite function classes that improves inversely with class stability.<n>We derive as a corollary a law of robustness for classification that extends the results of Bubeck and Sellke.<n>Experiments support our theory, while traditional norm-based measures remain largely uninformative.
  arXiv  Detail & Related papers  (2026-03-03T09:47:06Z)
• Unregularized Linear Convergence in Zero-Sum Game from Preference Feedback [50.89125374999765]
  We provide the first convergence guarantee for Optimistic Multiplicative Weights Update ($mathtOMWU$) in NLHF.<n>Our analysis identifies a novel marginal convergence behavior, where the probability of rarely played actions grows exponentially from exponentially small values.
  arXiv  Detail & Related papers  (2025-12-31T12:08:29Z)
• From Tail Universality to Bernstein-von Mises: A Unified Statistical Theory of Semi-Implicit Variational Inference [0.12183405753834557]
  Semi-implicit variational inference (SIVI) constructs approximate posteriors of the form $q() = int k(| z) r(dz)$<n>This paper develops a unified "approximation-optimization-statistics'' theory for such families.
  arXiv  Detail & Related papers  (2025-12-05T19:26:25Z)
• Stability and List-Replicability for Agnostic Learners [2.061173670995696]
  We prove that classes with infinite Littlestone dimension are not stably PAC learnable, even if we allow the stability parameter to depend on the excess error.<n>We also prove that only finite hypothesis classes are globally stable learnable, even if we restrict the agnostic setting to distributions with small population loss.
  arXiv  Detail & Related papers  (2025-01-09T15:59:15Z)
• 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)
• Beyond the Edge of Stability via Two-step Gradient Updates [49.03389279816152]
  Gradient Descent (GD) is a powerful workhorse of modern machine learning. GD's ability to find local minimisers is only guaranteed for losses with Lipschitz gradients. This work focuses on simple, yet representative, learning problems via analysis of two-step gradient updates.
  arXiv  Detail & Related papers  (2022-06-08T21:32:50Z)
• Lassoed Tree Boosting [53.56229983630983]
  We prove that a gradient boosted tree algorithm with early stopping faster than $n-1/4$ L2 convergence in the large nonparametric space of cadlag functions of bounded sectional variation. Our convergence proofs are based on a novel, general theorem on early stopping with empirical loss minimizers of nested Donsker classes.
  arXiv  Detail & Related papers  (2022-05-22T00:34:41Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  We use kernel Hilbert spaces for estimating the value function of an infinite-horizon discounted Markov reward process. We derive a non-asymptotic upper bound on the error with explicit dependence on the eigenvalues of the associated kernel operator. We prove minimax lower bounds over sub-classes of MRPs.
  arXiv  Detail & Related papers  (2021-09-24T14:48:20Z)
• Causal Inference Under Unmeasured Confounding With Negative Controls: A Minimax Learning Approach [84.29777236590674]
  We study the estimation of causal parameters when not all confounders are observed and instead negative controls are available. Recent work has shown how these can enable identification and efficient estimation via two so-called bridge functions.
  arXiv  Detail & Related papers  (2021-03-25T17:59:19Z)

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.