Teaching via Best-Case Counterexamples in the Learning-with-Equivalence-Queries Paradigm
Authors: Akash Kumar, Yuxin Chen, Adish Singla
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We characterize the query complexity for the optimal teacher in the Lw EQ paradigm, termed as learning-with-equivalence-queries teaching dimension (Lw EQ-TD). (see Section 3) II. We study the query complexity in the Lw EQ paradigm under different teaching settings: worst-case, random, and best-case, distinguished by the informativeness of counterexamples. We showcase the power of best-case counterexamples picked by the optimal teacher, in contrast to worst-case or random counterexamples, for different hypothesis classes, including Axes-aligned hyperplanes, Monotone monomials, and Orthogonal rectangles. (see Section 4) III. We establish new connections between Lw EQ-TD and Lf S-TD by studying Lw EQ-TD for different learner models based on the richness of their query functions. (see Section 5) |
| Researcher Affiliation | Academia | 1Max Planck Institute for Software Systems (MPI-SWS), 2UC San Diego, 3University of Chicago |
| Pseudocode | Yes | Algorithm 1: Query protocol between the learner and the teacher |
| Open Source Code | No | The paper does not provide any statement or link indicating that source code for the described methodology is publicly available. The ethics checklist indicates '[N/A]' for code-related questions. |
| Open Datasets | No | This is a theoretical paper that does not involve training models on datasets. The 'If you ran experiments...' section of the ethics checklist indicates '[N/A]' for data-related questions. |
| Dataset Splits | No | This is a theoretical paper that does not involve validation splits or experimental data. The 'If you ran experiments...' section of the ethics checklist indicates '[N/A]' for data-related questions. |
| Hardware Specification | No | This is a theoretical paper that does not describe experimental setups requiring hardware specifications. The 'If you ran experiments...' section of the ethics checklist indicates '[N/A]' for hardware details. |
| Software Dependencies | No | This is a theoretical paper that does not describe experimental setups requiring specific software dependencies with version numbers. The 'If you ran experiments...' section of the ethics checklist indicates '[N/A]' for software dependencies. |
| Experiment Setup | No | This is a theoretical paper that does not describe a practical experimental setup with hyperparameters or training configurations. The 'If you ran experiments...' section of the ethics checklist indicates '[N/A]' for training details. |