arXiv:2511.02644v2 cs.LG

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

David Kattermann, Lothar Sebastian Krapp

제출 2025-11-04

원문 초록

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.

요약

계산 가능한 PAC(CPAC) 학습 프레임워크에서 통계적 학습의 기본 정리(Fundamental Theorem of Statistical Learning)가 성립하지 않는 문제를 다루며, 재귀적으로 열거 가능한 표현 클래스(RER)와 CPAC 학습 가능성 사이의 깊은 연관성을 규명한다. RER 클래스만으로 비균일(nonuniform) CPAC 학습 가능성을 보장할 수 있음을 증명하고, 유효 VC-차원(effective VC-dimension)이 전통적 VC-차원보다 임의로 큰 값을 가질 수 있으나 계산 가능한 ERM이 존재하면 두 차원이 일치함을 보여 다양한 학습 가능성 개념을 분리하는 예시군을 구축한다.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2511.02644v2제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.