Optimal Learners for Realizable Regression: PAC Learning and Online Learning
Authors: Idan Attias, Steve Hanneke, Alkis Kalavasis, Amin Karbasi, Grigoris Velegkas
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we aim to characterize the statistical complexity of realizable regression both in the PAC learning setting and the online learning setting. Previous work had established the sufficiency of finiteness of the fat shattering dimension for PAC learnability and the necessity of finiteness of the scaled Natarajan dimension, but little progress had been made towards a more complete characterization since the work of Simon (SICOMP 97). |
| Researcher Affiliation | Collaboration | Idan Attias Ben-Gurion University of the Negev idanatti@post.bgu.ac.il Steve Hanneke Purdue University steve.hanneke@gmail.com Alkis Kalavasis Yale University alvertos.kalavasis@yale.edu Amin Karbasi Yale University, Google Research amin.karbasi@yale.edu Grigoris Velegkas Yale University grigoris.velegkas@yale.edu |
| Pseudocode | Yes | Algorithm 1 From orientation πto learner Aπ; Algorithm 2 Med Boost; Algorithm 3 Scaled SOA |
| Open Source Code | No | The paper does not contain any explicit statement about making its source code available, nor does it provide any links to a code repository. |
| Open Datasets | No | The paper is theoretical and focuses on mathematical characterizations of learnability; it does not conduct experiments on real-world datasets, nor does it mention any publicly available or open datasets for training purposes. |
| Dataset Splits | No | The paper is theoretical and does not describe empirical experiments or data, therefore it does not specify any training/validation/test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any empirical experiments, therefore it does not specify any hardware used for computations. |
| Software Dependencies | No | The paper is theoretical and does not describe any empirical experiments; thus, it does not list any specific software dependencies or version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any empirical experiments; therefore, it does not provide details about an experimental setup, hyperparameters, or system-level training settings. |