A Parameterized Theory of PAC Learning


  • Cornelius Brand TU Wien
  • Robert Ganian TU Wien
  • Kirill Simonov Hasso Plattner Institute




ML: Learning Theory, KRR: Computational Complexity of Reasoning, ML: Reinforcement Learning Theory


Probably Approximately Correct (i.e., PAC) learning is a core concept of sample complexity theory, and efficient PAC learnability is often seen as a natural counterpart to the class P in classical computational complexity. But while the nascent theory of parameterized complexity has allowed us to push beyond the P-NP "dichotomy" in classical computational complexity and identify the exact boundaries of tractability for numerous problems, there is no analogue in the domain of sample complexity that could push beyond efficient PAC learnability. As our core contribution, we fill this gap by developing a theory of parameterized PAC learning which allows us to shed new light on several recent PAC learning results that incorporated elements of parameterized complexity. Within the theory, we identify not one but two notions of fixed-parameter learnability that both form distinct counterparts to the class FPT - the core concept at the center of the parameterized complexity paradigm - and develop the machinery required to exclude fixed-parameter learnability. We then showcase the applications of this theory to identify refined boundaries of tractability for CNF and DNF learning as well as for a range of learning problems on graphs.




How to Cite

Brand, C., Ganian, R., & Simonov, K. (2023). A Parameterized Theory of PAC Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 37(6), 6834-6841. https://doi.org/10.1609/aaai.v37i6.25837



AAAI Technical Track on Machine Learning I