Find a witness or shatter: the landscape of computable PAC learning.

被引：0

作者：

Delle Rose, Valentino ^{[1
,2
]}

Kozachinskiy, Alexander ^{[2
,3
]}

Rojas, Cristobal ^{[1
,2
]}

Steifer, Tomasz ^{[1
,3
,4
]}

机构：

[1] PUC, Inst Math & Computat Engn, Santiago, Chile

[2] CENIA, Santiago, Chile

[3] IMFD, Santiago, Chile

[4] Polish Acad Sci, Inst Fundamental Technol Res, Warsaw, Poland

来源：

THIRTY SIXTH ANNUAL CONFERENCE ON LEARNING THEORY, VOL 195 | 2023年 / 195卷

关键词：

PAC learnability; CPAC learnability; VC dimension; Littlestone dimension; computability; foundations of machine learning;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

This paper contributes to the study of CPAC learnability-a computable version of PAC learning-by solving three open questions from recent papers. Firstly, we prove that every improperly CPAC learnable class is contained in a class which is properly CPAC learnable with polynomial sample complexity. This confirms a conjecture by Agarwal et al (COLT 2021). Secondly, we show that there exists a decidable class of hypotheses which is properly CPAC learnable, but only with uncomputably fast-growing sample complexity. This solves a question from Sterkenburg (COLT 2022). Finally, we construct a decidable class of finite Littlestone dimension which is not improperly CPAC learnable, strengthening a recent result of Sterkenburg (2022) and answering a question posed by Hasrati and Ben-David (ALT 2023). Together with previous work, our results provide a complete landscape for the learnability problem in the CPAC setting.

引用

页码：511 / 524

页数：14