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

2023/02/06 by Rose, Valentino Delle, Kozachinskiy, Alexander, Rojas, Cristobal +1 · 3 citations
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2302.04731

Abstract

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 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.

Cited by

• Samplability makes learning easier
• Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning
• Computable universal online learning

Related

• On the Computability of Robust PAC Learning
• On the Computability of Multiclass PAC Learning
• Computable learning of natural hypothesis classes
• A Parameterized Theory of PAC Learning
• Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning