Active Classification with Few Queries under Misspecification
Authors: Vasilis Kontonis, Mingchen Ma, Christos Tzamos
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main algorithmic result is the first query-efficient algorithm for learning halfspaces under the popular Massart noise model. With an arbitrary dataset corrupted with Massart noise at noise rate η, our algorithm uses only poly log(1/ϵ) threshold statistical queries and computes an (η + ϵ)-accurate labeling in polynomial time. For the harder case of agnostic noise, we show that it is impossible to beat O(1/ϵ) query complexity even for the much simpler problem of learning singletons (and thus for learning halfspaces) using a reduction from agnostic distributed learning. This paper is theoretical and does not contain experiments. |
| Researcher Affiliation | Collaboration | Vasilis Kontonis UT-Austin vasilis@cs.utexas.edu Mingchen Ma University of Wisconsin-Madison mingchen@cs.wisc.edu Christos Tzamos University of Athens and Archimedes AI ctzamos@gmail.com |
| Pseudocode | Yes | Algorithm 1 WEAKLY LEARNING HALFSPACES (Labeling 1/d fraction of examples via TSQ) Algorithm 2 STRONG LEARNING HALFSPACES (Label S with few queries up to η + ϵ error ) Algorithm 3 APPROXIMATE AGNOSTIC LEARNING(Learning a labeling up to O(opt) error) |
| Open Source Code | No | This paper is theoretical and does not contain experiments. (from NeurIPS checklist, implying no code release for methodology) |
| Open Datasets | No | This paper is theoretical and does not contain experiments. (from NeurIPS checklist). The paper uses abstract 'set S of n unlabeled examples' or 'dataset S' for theoretical formulation, not specific datasets for experiments. |
| Dataset Splits | No | This paper is theoretical and does not contain experiments. (from NeurIPS checklist). |
| Hardware Specification | No | This paper is theoretical and does not contain experiments. (from NeurIPS checklist). |
| Software Dependencies | No | This paper is theoretical and does not contain experiments. (from NeurIPS checklist). |
| Experiment Setup | No | This paper is theoretical and does not contain experiments. (from NeurIPS checklist). |