A Parameterized Theory of PAC Learning
Authors: Cornelius Brand, Robert Ganian, Kirill Simonov
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | As our core contribution, we fill this gap by developing a theory of parameterized PAC learning... 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. |
| Researcher Affiliation | Academia | Cornelius Brand1, Robert Ganian1, Kirill Simonov2 1 Algorithms and Complexity Group, TU Wien, Austria 2Chair for Algorithm Engineering, Hasso Plattner Institute, Germany {cbrand, rganian}@ac.tuwien.ac.at, kirill.simonov@hpi.de |
| Pseudocode | No | The paper describes theoretical concepts and proofs but does not include any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not mention providing open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve empirical training on datasets. No concrete access information for a publicly available or open dataset is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical validation. No specific dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not specify software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any specific experimental setup details or hyperparameters. |