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

Simple item page
dc.article.numberarXiv:2302.04731
dc.catalogadoraba
dc.contributor.authorDelle Rose, Valentino
dc.contributor.authorKozachinskiy, Alexander
dc.contributor.authorRojas González, Luis Cristóbal
dc.contributor.authorSteifer, Tomasz
dc.date.accessioned2023-08-29T16:35:30Z
dc.date.available2023-08-29T16:35:30Z
dc.date.issued2023
dc.description.abstractThis 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 hypothesis 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.
dc.description.funderEuropean Union
dc.fechaingreso.objetodigital2023-08-29
dc.fuente.origenWOS
dc.identifier.doi10.48550/arXiv.2302.04731
dc.identifier.urihttps://doi.org/10.48550/arXiv.2302.04731
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/74543
dc.identifier.wosidPPRN:36866201
dc.information.autorucInstituto de Ingeniería Matemática y Computacional; Rojas González, Luis Cristóbal; 0000-0002-9037-6102; 1182858
dc.language.isoen
dc.nota.accesoContenido completo
dc.revistaArxiv
dc.rightsacceso abierto
dc.subject.ddc510
dc.subject.deweyMatemática física y químicaes_ES
dc.titleFind a witness or shatter: the landscape of computable PAC learning
dc.typepreprint
sipa.codpersvinculados1182858
sipa.indexWOS
sipa.trazabilidadWOS;2023-07-06
sipa.trazabilidadORCID;2023-08-28
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Find a witness or shatter.pdf
Size:
184.84 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Artículos de revistas