On the Complexity of Learning a Class Ratio from Unlabeled Data
Authors: Benjamin Fish, Lev Reyzin
JAIR 2020 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we formally define this class and resolve foundational questions regarding the computational complexity of CR learning and characterize its relationship to PAC learning. Among our results, we show, perhaps surprisingly, that for finite VC classes what can be efficiently CR learned is a strict subset of what can be learned efficiently in PAC, under standard complexity assumptions. We also show that there exist classes of functions whose CR learnability is independent of ZFC, the standard set theoretic axioms. This implies that CR learning cannot be easily characterized (like PAC by VC dimension). |
| Researcher Affiliation | Academia | Benjamin Fish EMAIL Mila Quebec AI Institute 6666 St-Urbain, #200, Montreal, QC, H2S 3H1 Lev Reyzin EMAIL Department of Mathematics, Statistics, and Computer Science University of Illinois at Chicago 851 S Morgan St, Chicago, IL 60607 |
| Pseudocode | No | The paper describes algorithms and proofs in narrative text, but does not include any explicitly labeled pseudocode blocks or algorithms formatted as code. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code, nor does it provide links to code repositories or mention code in supplementary materials. |
| Open Datasets | No | The paper is theoretical and discusses abstract concepts like distributions over domains (e.g., "distribution D over X"). It does not use or provide access information for any specific named datasets. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments using specific datasets, therefore it does not discuss dataset splits. |
| Hardware Specification | No | The paper focuses on theoretical aspects of learning and does not describe any experimental setup that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe any experimental setup that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup, hyperparameters, or training configurations. |