Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Active Classification with Few Queries under Misspecification
Authors: Vasilis Kontonis, Mingchen Ma, Christos Tzamos
NeurIPS 2024 | Venue PDF | 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 EMAIL Mingchen Ma University of Wisconsin-Madison EMAIL Christos Tzamos University of Athens and Archimedes AI EMAIL |
| 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). |