Active Learning Polynomial Threshold Functions
Authors: Omri Ben-Eliezer, Max Hopkins, Chutong Yang, Hantao Yu
NeurIPS 2022 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We initiate the study of active learning polynomial threshold functions (PTFs). While traditional lower bounds imply that even univariate quadratics cannot be non-trivially actively learned, we show that allowing the learner basic access to the derivatives of the underlying classifier circumvents this issue and leads to a computationally efficient algorithm for active learning degree-d univariate PTFs in O(d3 log(1/εδ)) queries. We prove that if the learner is allowed access to sign(p(i)(x)) (the i-th order derivative of p), PTFs are learnable in O(log(1/ε)) queries, but require Ω(1/ε) queries if the learner is missing access even to a single relevant derivative. |
| Researcher Affiliation | Academia | Omri Ben-Eliezer Department of Mathematics Massachusetts Institute of Technology EMAIL Max Hopkins Department of Computer Science and Engineering University of California, San Diego EMAIL Chutong Yang Department of Computer Science Stanford University EMAIL Hantao Yu Department of Computer Science Columbia University EMAIL |
| Pseudocode | Yes | Algorithm 1: ITERATIVE-ALGORITHM(f, S) and Algorithm 2: BATCH-KLMZ(S, m) |
| Open Source Code | No | The paper does not mention releasing source code or provide a link to a code repository. The ethics checklist states 'Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A]'. |
| Open Datasets | No | This is a theoretical paper that does not perform experiments with datasets. Therefore, it does not mention public datasets for training. |
| Dataset Splits | No | This is a theoretical paper focusing on algorithmic complexity and proofs, not empirical validation. It does not mention dataset splits for training, validation, or testing. |
| Hardware Specification | No | As a theoretical paper, there are no experiments conducted that would require hardware specifications. |
| Software Dependencies | No | As a theoretical paper, there are no experiments conducted that would require specific software dependencies and versions. |
| Experiment Setup | No | As a theoretical paper, there are no experiments conducted that would require detailed experimental setup information like hyperparameters. |